{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "a0657324-1222-4fa0-bc0c-163c928b2c72",
   "metadata": {},
   "source": [
    "# 快速傅里叶变换"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2ee9caa0-4198-4c9b-9e8e-22d21e33c8ca",
   "metadata": {},
   "source": [
    "姓名：石庆波\n",
    "---\n",
    "学号：202052320106\n",
    "---"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "1bd77fef-0f1a-44da-9735-bdc0ff42a3e4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAABIcAAAEvCAYAAADfBqG/AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMywgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/MnkTPAAAACXBIWXMAAAsTAAALEwEAmpwYAAAsOklEQVR4nO3df4xld30f/Pdnf0AXO7BQ1o69UOEKd1SSqFggEstKNG7arIv0CBMJPVCpcRQkO2kiFSkysVtVoKA0Vq00PK0a+jhPkF2pMayoWSxIcajpxq1EAnbXwiZki0Op47GFRWAIaya2d/b7/DF3zHg9s/PjnnvvmTmvlzSamXPvnPO973vv93z2s+ecW621AAAAADBM+2Y9AAAAAABmR3MIAAAAYMA0hwAAAAAGTHMIAAAAYMA0hwAAAAAGTHMIAAAAYMAOTHNjhw8fbm984xunuck97ZlnnslFF10062HsKTLtnky7Jc/uybRbDz300Ldaa0dmPQ5eTA3WLfNG92TaLXl2T6bdkmf3xq3BptocuvTSS/Pggw9Oc5N72smTJzM/Pz/rYewpMu2eTLslz+7JtFtV9X9mPQZeSg3WLfNG92TaLXl2T6bdkmf3xq3BNj2trKpeX1X/raq+WlVfqap/Nlr+mqr6XFV9bfT91eMMBACAH1CDAQDTspVrDp1N8quttb+b5CeS/HJVvSnJLUnub61dmeT+0e971olTC7nmts/nils+k2tu+3xOnFqY9ZAA2OXsW9iEGgwAmIpNm0Ottadaa/9z9PP3knw1ydEk70hy1+hudyW5fkJjnLkTpxZy6z2PZGFxKS3JwuJSbr3nEUU8ADtm38Jm1GAAwLRs69PKquoNSa5K8idJLm2tPZWsFC9JLul8dD1x+32ns/T88ouWLT2/nNvvOz2jEQGw29m3sB1DrcEAgOmo1trW7lh1cZI/SvIbrbV7qmqxtXZ4ze3faa295Jz3qroxyY1JcuTIkbccP368k4FP089/9pkNb7vzutldYf3MmTO5+OKLZ7b9vUim3ZNpt+TZvVll2td9y7iuvfbah1prb531OPaSIddgfWUu7p5MuyXP7sm0W/Ls3rg12JY+rayqDib5z0n+U2vtntHib1bVZa21p6rqsiRPr/e3rbU7ktyRJHNzc203XpH86B9/PguLSy9dfvjQTK+w7grv3ZNp92TaLXl2b1aZ9nXfQr8MvQbrK3Nx92TaLXl2T6bdkmf/bOXTyirJ7yX5amvt36y56d4kN4x+viHJp7ofXj/cfGwuhw7uf9GyQwf35+ZjczMaEQC7nX0Lm1GDAQDTspUjh65J8k+SPFJVD4+W/fMktyU5XlXvTfJ4kndNZIQ9cP1VR5Mk7//El/Pc8rkcPXwoNx+be2E5AGyXfQtbMPgaDACYjk2bQ621/5GkNrj5p7sdTn9df9XR3P3Fx5MkH7/p6hmPBoC9wL6FC1GDAQDTsq1PKwMAAABgb9EcAgAAABgwzSEAAACAAdMcAgAAABgwzSEAAACAAdMcAgAAABgwzSEAAACAAdMcAgAAABgwzSEAAACAAdMcAgAAABgwzSEAAACAAdMcAgAAABgwzSEAAACAAdMcAgAAABgwzSEAAACAAdMcAgAAABgwzSEAAACAAdMcAgAAABgwzSEAAACAAdMcAgAAABiwTZtDVfXRqnq6qh5ds+yDVbVQVQ+Pvt4+2WECAAyLGgwAmJatHDl0Z5Lr1ln+2621N4++/qDbYQEADN6dUYMBAFOwaXOotfZAkm9PYSwAAIyowQCAaanW2uZ3qnpDkk+31n509PsHk/x8kr9K8mCSX22tfWeDv70xyY1JcuTIkbccP368i3HPxG/+yVKS5NYfPzTjkaw4c+ZMLr744lkPY0+Rafdk2i15dm/WmfZt3zKua6+99qHW2ltnPY69Qg3WT7OeN/YimXZLnt2Tabfk2b1xa7CdNocuTfKtJC3Jh5Jc1lr7hc3WMzc3106fPr3Tsc7c//3/fiFJ8vGbrp7xSFacPHky8/Pzsx7GniLT7sm0W/Ls3qwz7du+ZVxVpTnUITVYP8163tiLZNoteXZPpt2SZ/fGrcF29GllrbVvttaWW2vnkvxukrftdAAAAGyNGgwAmIQdNYeq6rI1v74zyaMb3RcAgG6owQCASTiw2R2q6u4k80leW1VPJPlAkvmqenNWDmn+RpKbJjdEAIDhUYMBANOyaXOotfaedRb/3gTGAgDAiBoMAJiWHZ1WBgAAAMDeoDkEAAAAMGCaQwAAAAADpjkEAAAAMGCaQwAAAAADpjkEAAAAMGCaQwAAAAADpjkEAAAAMGCaQwAAAAADpjkEAAAAMGCaQwAAAAADpjkEAAAAMGCaQwAAAAADpjkEAAAAMGCaQwAAAAADpjkEAAAAMGCaQwAAAAADpjkEAAAAMGCaQwAAAAADtmlzqKo+WlVPV9Wja5a9pqo+V1VfG31/9WSHCQAwLGowAGBatnLk0J1Jrjtv2S1J7m+tXZnk/tHvTMGJUwu55rbP54pbPpNfPfn9nDi1MOshAexKq/Ppz3/2mVxz2+fNp/TRnVGD9YYaDGB86q/+2rQ51Fp7IMm3z1v8jiR3jX6+K8n13Q6L9Zw4tZBb73kkC4tLaUn+8q9bbr3nEW8ogG1aO58mycLikvmU3lGD9YcaDGB86q9+2+k1hy5trT2VJKPvl3Q3JDZy+32ns/T88ouWLT2/nNvvOz2jEQHsTuZTdjE12AyYMwDGZy7ttwOT3kBV3ZjkxiQ5cuRITp48OelNTsziqMM5q8ew2mFdb/luzrVPzpw5I8uOybRb8uxGn+bTWe9b2Lv2Ug02a32aM/Yq+7duybN7Mh2fubTfdtoc+mZVXdZae6qqLkvy9EZ3bK3dkeSOJJmbm2vz8/M73OTsfeT0F5Ik8/NXz2T7R//48+u+oY4ePpTdnGufnDx5UpYdk2m35NmNPs2ns963sOsMsgabtT7NGXuV/Vu35Nk9mY7PXNpvOz2t7N4kN4x+viHJp7oZDhdy87G5HDq4/0XLDh3cn5uPzc1oRAC7k/mUXUwNNgPmDIDxmUv7bdMjh6rq7iTzSV5bVU8k+UCS25Icr6r3Jnk8ybsmOUhWXH/V0STJ+z/x5Ty3fC5/829U/uU7fuyF5QBszfnz6dHDh3LzsTnzKb2iBusPNRjA+NRf/bZpc6i19p4NbvrpjsfCFlx/1dHc/cXHkyS/NPds5r2RAHZkdT5dXFzMfb/292c9HHgJNVi/qMEAxqf+6q+dnlYGAAAAwB6gOQQAAAAwYJpDAAAAAAOmOQQAAAAwYJpDAAAAAAOmOQQAAAAwYJpDAAAAAAOmOQQAAAAwYJpDAAAAAAOmOQQAAAAwYJpDAAAAAAOmOQQAAAAwYJpDAAAAAAOmOQQAAAAwYJpDAAAAAAOmOQQAAAAwYJpDAAAAAAOmOQQAAAAwYJpDAAAAAAOmOQQAAAAwYAfG+eOq+kaS7yVZTnK2tfbWLgYFAMDG1GAAQJfGag6NXNta+1YH6wEAYOvUYABAJ5xWBgAAADBg4zaHWpI/rKqHqurGLgYEAMCm1GAAQGfGPa3smtbak1V1SZLPVdWftdYeWHuHUcFyY5IcOXIkJ0+eHHOTs7O4uJQkM38Mq+M4c2Z55mPZa86cOSPTjsm0W/Ls1uLiUpaXZzuX9mXfwq4zqBqsL9Rgk2P/1i15dk+m3elD/cVLjdUcaq09Ofr+dFV9Msnbkjxw3n3uSHJHkszNzbX5+flxNjlTHzn9hSTJ/PzVvRjHxRc/m92cZx+dPHlSph2Tabfk2a2PnP5CFhcXZ5ppX/Yt7C5Dq8H6Qg02OfZv3ZJn92TanT7UX7zUjk8rq6qLquqHVn9O8jNJHu1qYAAAvJQaDADo2jhHDl2a5JNVtbqe32+tfbaTUQEAsBE1GADQqR03h1prX0/y9zocCwAAm1CDAQBd81H2AAAAAAOmOQQAAAAwYJpDAAAAAAM21kfZA8Ny4tRCbr/vdJ5cXMrlhw/l5mNzuf6qozNfFwDAXqYGAyZNcwjYkhOnFnLrPY9k6fnlJMnC4lJuveeRJNl2QdHlugAA9jI1GDANTisDtuT2+06/UEisWnp+Obffd3qm6wIA2MvUYMA0aA4BW/Lk4tK2lk9rXQAAe5kaDJgGzSFgSy4/fGhby6e1LgCAvUwNBkyD5hCwJTcfm8uhg/tftOzQwf25+djcTNcFALCXqcGAaXBBamBLVi9S+P5PfDnPLZ/L0TE+3aLLdQEA7GVqMGAaNIeALbv+qqO5+4uPJ0k+ftPVvVkXAMBepgYDJs1pZQAAAAAD5sgh6IETpxZy+32n8+TiUi53eG+veG4AYO+yn+8vzw1Ml+YQzNiJUwu59Z5HsvT8cpJkYXEpt97zSJLYAc6Y5wYA9i77+f7y3MD0Oa0MZuz2+06/sONbtfT8cm6/7/SMRsQqzw0A7F328/3luYHp0xyCGXtycWlby5kezw0A7F328/3luYHp0xyCGbv88KFtLWd6PDcAsHfZz/eX5wamT3MIZuzmY3M5dHD/i5YdOrg/Nx+bm9GIWOW5AYC9y36+vzw3MH0uSA0ztnpRvfd/4st5bvlcjvo0ht7w3ADA3mU/31+eG5g+zSHogeuvOpq7v/h4kuTjN10949GwlucGAPYu+/n+8tzAdI11WllVXVdVp6vqsaq6patBAQCwMTUYANClaq3t7A+r9if5X0n+YZInknwpyXtaa3+60d+8/LIr2+U3fDirW9xXybmWVLKlZfurstzalu/f9XoP7Ku85hUH89xyy+LS8zMcb1JVOXuuvbCNWWez19c7jW2tvr4OHtifhcWlXo73B6+35JWHDuY7339+rPX25z218XrXe8yzfj3u5td539a7v1aWbfV1MKnxdvWe6kPmT931vjz71NcqTMxOa7DLbviwuWXM9a5Xg/VxvHsp82msd7v1yKweQ5e14m7598RuqBWHtN4utrX2/odfsXFtvduy6UPmC3eOV4ONc1rZ25I81lr7epJU1ceSvCPJhoVJ8oPBJysPbDvLlkeNrHHWMc56z55refrMc8km95v8eJOM1r183vdZZbPX1zuNbZ3/+urjeH/weku+8/3nx15vf95TG693vcc869fjbn6d9229y2sWbuV1MKnxdvWe6kvmTNyOarDE3DLueterwfo43r2U+TTWu916ZFaPoctacbf8e2I31IpDWm8X21p7/wvV1rstm75kPo5xmkNHk/zFmt+fSPLjF/qD133v6fyr//47Y2wSAOizn5v1AIZBDQYAvMi4Ndg41xxa73Cll/SrqurGqnqwqh4cY1sAAKxQgwEAnRrnyKEnkrx+ze+vS/Lk+Xdqrd2R5I5k5Xz3X/vJfzrGJgGAXvv6+2Y9giFQgwEALzZmDTbOkUNfSnJlVV1RVS9L8u4k9441GgAANqMGAwA6teNPK0uSqnp7kg8n2Z/ko62137jQ/fe/4lXtwCsv+cHB0C0/uPz2dpZt9/4drbedO3f23LPPfGffyy96de3bd2BW423nzp1NkqrRGHqQzZ5Z76oZPIYXXl8vO/Sq2n/gZb3LZs2yF16D+/Yd2PT+yYbb78t7asePeRbjXTXJHCb9GHq03pXnte2rffv3zXK823pP9Tzzs999Osvf/+7qvZiQHdVgr7pktq+RaW5r0u/V9WqwHo53qtsadx3ZYH1TGO+O65FpZXP+OLdSK66X6Zr7XXC/06PXSK9qxVU9yWa3zy3t3PK5pM5tWlv3ZLwzX+8WtnX2r8arwcZqDm17Y1UPttbeOrUN7nHy7J5MuyfTbsmzezLtljz7yfPSLXl2T6bdkmf3ZNoteXZv3EzHOa0MAAAAgF1OcwgAAABgwKbdHLpjytvb6+TZPZl2T6bdkmf3ZNotefaT56Vb8uyeTLslz+7JtFvy7N5YmU71mkMAAAAA9IvTygAAAAAGbCLNoap6V1V9parOVdVb1yx/Q1UtVdXDo6//sOa2t1TVI1X1WFX926ra8Uew7UUbZTq67dZRbqer6tia5TLdoqr6YFUtrHltvn3Nbevmy4VV1XWjzB6rqltmPZ7dqqq+MXofP1xVD46WvaaqPldVXxt9f/Wsx9lXVfXRqnq6qh5ds2zD/LzfN7dBpubQnlCDdU8NNjnmjslQg41P/TU+NVj3Jl2DTerIoUeT/GySB9a57c9ba28eff3imuUfSXJjkitHX9dNaGy71bqZVtWbkrw7yY9kJbPfqar9o5tluj2/vea1+QfJpvmygVFG/z7JP0rypiTvGWXJzlw7el2u/qPkliT3t9auTHL/6HfWd2deOvetm5/3+5bdmfX3J+bQflCDdU8NNlnmjg6pwTql/hrPnVGDde3OTLAGm0hzqLX21dba6a3ev6ouS/LK1toX2spFkP5jkusnMbbd6gKZviPJx1prz7bW/neSx5K8TaadWTffGY9pN3hbksdaa19vrT2X5GNZyZJuvCPJXaOf74r39oZaaw8k+fZ5izfKz/t9CzbIdCMynTI1WPfUYDNh7tg5NdjkqL+2QQ3WvUnXYLO45tAVVXWqqv6oqn5ytOxokifW3OeJ0TI2dzTJX6z5fTU7mW7fr1TVl0eH660e4rhRvlyY3LrTkvxhVT1UVTeOll3aWnsqSUbfL5nZ6HanjfLzuh2PObT/1GDdUoN1w9zRLdl1Q/01GWqwyehkHj2w061X1X9N8sPr3PQvWmuf2uDPnkryt1prf1lVb0lyoqp+JMl652EP7mPUdpjpRtnJ9DwXyjcrh39/KCsZfSjJbyX5hchxp+TWnWtaa09W1SVJPldVfzbrAe1hXrc7Zw6dIjVY99Rgk6P+mjrZdUP9NV1etzvX2Ty64+ZQa+0f7OBvnk3y7Ojnh6rqz5P8nax0sV635q6vS/LkTse2W+0k06xk9/o1v69mJ9PzbDXfqvrdJJ8e/bpRvlyY3DrSWnty9P3pqvpkVg4H/WZVXdZae2p0+sLTMx3k7rNRfl63O9Ra++bqz+bQyVODdU8NNjnqr6mTXQfUXxOjButYlzXYVE8rq6ojqxdBqqq/nZUL9H19dEjZ96rqJ6qqkvxcko3+l4YXuzfJu6vq5VV1RVYy/aJMt2c0Oa16Z1YuPplskO+0x7cLfSnJlVV1RVW9LCsXQ7t3xmPadarqoqr6odWfk/xMVl6b9ya5YXS3G+K9vV0b5ef9vkPm0P5Tg02EGmxM5o6JUIONSf01UWqwjnU5j+74yKFNBvjOJP8uyZEkn6mqh1trx5L8VJJfr6qzSZaT/GJrbfWCSr+UlatvH0ryX0ZfjGyUaWvtK1V1PMmfJjmb5Jdba8ujP5Pp1v3rqnpzVg61+0aSm5Jkk3zZQGvtbFX9SpL7kuxP8tHW2ldmPKzd6NIkn1z5t0UOJPn91tpnq+pLSY5X1XuTPJ7kXTMcY69V1d1J5pO8tqqeSPKBJLdlnfy837dmg0znzaH9oAbrnhpsotRfHVODdUL91QE1WPcmXYPVyocoAAAAADBEs/i0MgAAAAB6QnMIAAAAYMA0hwAAAAAGTHMIAAAAYMA0hwAAAAAGTHMIAAAAYMA0hwAAAAAGTHMIAAAAYMAOTHNjhw8fbm984xunuck97ZlnnslFF10062HsKTLtnky7Jc/uybRbDz300Ldaa0dmPQ5eTA3WLfNG92TaLXl2T6bdkmf3xq3BptocuvTSS/Pggw9Oc5N72smTJzM/Pz/rYewpMu2eTLslz+7JtFtV9X9mPQZeSg3WLfNG92TaLXl2T6bdkmf3xq3BNj2trKpeX1X/raq+WlVfqap/Nlr+mqr6XFV9bfT91eMMBACAH1CDAQDTspVrDp1N8quttb+b5CeS/HJVvSnJLUnub61dmeT+0e973olTC7nmts/nils+k2tu+3xOnFqY9ZAA2KXsU9iEGgwAmIpNm0Ottadaa/9z9PP3knw1ydEk70hy1+hudyW5fkJj7I0TpxZy6z2PZGFxKS3JwuJSbr3nEcU8ANtmn8Jm1GAAwLRs69PKquoNSa5K8idJLm2tPZWsFC9JLul8dD1z+32ns/T88ouWLT2/nNvvOz2jEQGwW9mnsB1Dr8EAgMmq1trW7lh1cZI/SvIbrbV7qmqxtXZ4ze3faa295Jz3qroxyY1JcuTIkbccP368k4HPws9/9pkNb7vzuulfaf3MmTO5+OKLp77dvUym3ZNpt+TZvVll2rd9Sleuvfbah1prb531OPYSNVj/mIu7J9NuybN7Mu2WPLs3bg22pU8rq6qDSf5zkv/UWrtntPibVXVZa+2pqrosydPr/W1r7Y4kdyTJ3Nxc281XJD/6x5/PwuLSS5cfPjSTK627wnv3ZNo9mXZLnt2bVaZ926fQT2qwfjIXd0+m3ZJn92TaLXn2z1Y+rayS/F6Sr7bW/s2am+5NcsPo5xuSfKr74fXLzcfmcujg/hctO3Rwf24+NjejEQGwW9mnsBk1GAAwLVs5cuiaJP8kySNV9fBo2T9PcluS41X13iSPJ3nXREbYI9dfdTRJ8v5PfDnPLZ/L0cOHcvOxuReWA8BW2aewBWowAGAqNm0Otdb+R5La4Oaf7nY4/Xf9VUdz9xcfT5J8/KarZzwaAHYz+xQuRA0GAEzLtj6tDAAAAIC9RXMIAAAAYMA0hwAAAAAGTHMIAAAAYMA0hwAAAAAGTHMIAAAAYMA0hwAAAAAGTHMIAAAAYMA0hwAAAAAGTHMIAAAAYMA0hwAAAAAGTHMIAAAAYMA0hwAAAAAGTHMIAAAAYMA0hwAAAAAGTHMIAAAAYMA0hwAAAAAGTHMIAAAAYMA0hwAAAAAGTHMIAAAAYMA2bQ5V1Uer6umqenTNsg9W1UJVPTz6evtkhwkAMCxqMABgWrZy5NCdSa5bZ/lvt9bePPr6g26HBQAweHdGDQYATMGmzaHW2gNJvj2FsQAAMKIGAwCmZZxrDv1KVX15dMjzqzsbEQAAF6IGAwA6Va21ze9U9YYkn26t/ejo90uTfCtJS/KhJJe11n5hg7+9McmNSXLkyJG3HD9+vJuRz9Bv/slSkuTWHz8003GcOXMmF1988UzHsNfItHsy7ZY8uzfrTPuyT+nKtdde+1Br7a2zHsdeoQbrp1nPG3uRTLslz+7JtFvy7N64NdiBnfxRa+2bqz9X1e8m+fQF7ntHkjuSZG5urs3Pz+9kk73ykdNfSJLMz18903GcPHkyeyHPPpFp92TaLXl2b9aZ9mWfwu4w9BqsL2Y9b+xFMu2WPLsn027Js392dFpZVV225td3Jnl0o/sCANANNRgAMAmbHjlUVXcnmU/y2qp6IskHksxX1ZuzckjzN5LcNLkhAgAMjxoMAJiWTZtDrbX3rLP49yYwFgAARtRgAMC0jPNpZQAAAADscppDAAAAAAOmOQQAAAAwYJpDAAAAAAOmOQQAAAAwYJpDAAAAAAOmOQQAAAAwYJpDAAAAAAOmOQQAAAAwYJpDAAAAAAOmOQQAAAAwYJpDAAAAAAOmOQQAAAAwYJpDAAAAAAOmOQQAAAAwYJpDAAAAAAOmOQQAAAAwYJpDAAAAAAOmOQQAAAAwYJpDAAAAAAO2aXOoqj5aVU9X1aNrlr2mqj5XVV8bfX/1ZIcJADAsajAAYFq2cuTQnUmuO2/ZLUnub61dmeT+0e9MyYlTC7nmts/n5z/7TK657fM5cWph1kMC2HXMpewCd0YN1ivmDYDxmEf7a9PmUGvtgSTfPm/xO5LcNfr5riTXdzssNnLi1EJuveeRLCwuJUkWFpdy6z2PeFMBbIO5lN1ADdYv5g2A8ZhH+61aa5vfqeoNST7dWvvR0e+LrbXDa27/Tmtt3cOaq+rGJDcmyZEjR95y/PjxDoY9W7/5Jysv5lt//NDUt/2rJ7+fv/zrlz5nf/NvVH5r/hVTH89ec+bMmVx88cWzHsaeItNuybMbfZpLZ7lPmYRrr732odbaW2c9jr1CDdYffZo39iL7t27Js3syHZ95dLLGrcEOdDmY9bTW7khyR5LMzc21+fn5SW9y4j5y+gtJkvn5q6e+7W9/9jPrL//rlr2Q7aydPHlSjh2Tabfk2Y0+zaWz3Kewt+3FGmyW+jRv7EX2b92SZ/dkOj7zaL/t9NPKvllVlyXJ6PvT3Q2JC7n88Pr/s7zRcgBeylzKLqYGmxHzBsB4zKP9ttPm0L1Jbhj9fEOST3UzHDZz87G5HDq4/0XLDh3cn5uPzc1oRAC7j7mUXUwNNiPmDYDxmEf7bdPTyqrq7iTzSV5bVU8k+UCS25Icr6r3Jnk8ybsmOUh+4PqrjiZJ3v+JL+e55XM5evhQbj4298JyADZnLmU3UIP1i3kDYDzm0X7btDnUWnvPBjf9dMdjYYuuv+po7v7i41lcXMx9v/b3Zz0cgF3JXErfqcH6x7wBMB7zaH/t9LQyAAAAAPYAzSEAAACAAdMcAgAAABgwzSEAAACAAdMcAgAAABgwzSEAAACAAdMcAgAAABgwzSEAAACAAdMcAgAAABgwzSEAAACAAdMcAgAAABgwzSEAAACAAdMcAgAAABgwzSEAAACAAdMcAgAAABgwzSEAAACAAdMcAgAAABgwzSEAAACAAdMcAgAAABiwA+P8cVV9I8n3kiwnOdtae2sXgwIAYGNqMACgS2M1h0auba19q4P1AACwdWowAKATTisDAAAAGLBxm0MtyR9W1UNVdWMXAwIAYFNqMACgM+OeVnZNa+3Jqrokyeeq6s9aaw+svcOoYLkxSY4cOZKTJ0+OucnZW1xcSpKZPpbFxaUsLy/viTz75MyZMzLtmEy7Jc9u9WEu7cM+hV1pkDVYH/Rh3tiL7N+6Jc/uybQ75tF+Gqs51Fp7cvT96ar6ZJK3JXngvPvckeSOJJmbm2vz8/PjbLIXPnL6C0mS+fmrZzqGxcXF7IU8++TkyZMy7ZhMuyXPbvVhLu3DPoXdZ6g1WB/0Yd7Yi+zfuiXP7sm0O+bRftrxaWVVdVFV/dDqz0l+JsmjXQ0MAICXUoMBAF0b58ihS5N8sqpW1/P7rbXPdjIqAAA2ogYDADq14+ZQa+3rSf5eh2MBAGATajAAoGs+yh4AAABgwDSHAAAAAAZMcwgAAABgwDSHAAAAAAZsnE8rAwbqxKmF3H7f6Ty5uJTLDx/Kzcfmcv1VR6e+DgCAIVGDAZOiOQRsy4lTC7n1nkey9PxykmRhcSm33vNIkmy5sOhiHQAAQ6IGAybJaWXAttx+3+kXCopVS88v5/b7Tk91HQAAQ6IGAyZJcwjYlicXl7a1fFLrAAAYEjUYMEmaQ8C2XH740LaWT2odAABDogYDJklzCNiWm4/N5dDB/S9adujg/tx8bG6q6wAAGBI1GDBJLkgNbMvqxQrf/4kv57nlczm6g0+56GIdAABDogYDJklzCNi26686mru/+HiS5OM3XT2zdQAADIkaDJgUzSHokROnFnL7fafz5OJSLvc/Ob3gOQGAvc/+vn88JzBdmkPQEydOLeTWex554eNFFxaXcus9jySJHeGMeE4AYO+zv+8fzwlMnwtSQ0/cft/pF3aAq5aeX87t952e0YjwnADA3md/3z+eE5g+zSHoiScXl7a1nMnznADA3md/3z+eE5g+p5Vt0dpzXvdVUlW54pbPOP+Vzlx++FAW1tnhXX740AxGQ+I5YbJW9ysLi0vZX8lVv/6HWfz+8/YrAFNmf98/nhOYPkcObcHqOa8Li0tpSZZbcvZcS8sPzn89cWph1sNkl7v52FwOHdz/omWHDu7PzcfmZjQiPCdMytr9SrKyX/nO95+3XwGYAfv7/vGcwPRpDm3Beue8ruX8V7pw/VVH85s/+2N52f6Vt+XRw4fymz/7Y44emCHPCZNivwLQH/b3/eM5gelzWtkFnDi1kA/e+5UsLj2/6X0XFpfyhls+k6MTPh1g7WkIFach7DXXX3U0d3/x8STJx2+6esajIfGc7EXnnybckqmcJrx2/t6Kae1XgK1Rg+1t9vf94znZe8yj/TZWc6iqrkvy/yTZn+T/a63d1smoJuT8Zs++Ss61ZH9VlltLZeUfCeNYWFzK+z7+cN738YfXXe/qNney7HwtK6chnL/dVa9+xcF84P/6EW8yYLDOL0LOn0+X1yxYbx690H5iu/P5Tq0d12bbMu8Px26rwfrgxdf52vl7Otm4Blu9v6YuMHSbHWix2Ty61Xla7dOdam1nFWtV7U/yv5L8wyRPJPlSkve01v50o795+WVXtstv+PCOC+txd+RMN/O9tN5pbutl+/fl8KEDeW65vaSR2afxHthXec0rDubggf0v+Yf3dtex1cc6i9fN6m37K3nloYP5zvefn/lrZC+8zqe53qGbduZP3fW+PPvU12paj2+IdlqDXXbDhwc9t8zKkDPfbevdXysfOnP2XOtk+32uFdd7rH18LndDrTik9W51W7M2xMz3VbJw53g12DhHDr0tyWOtta8nSVV9LMk7kmxYmCQvfsGs7qi3umx51MjayTpYMc3M99J6p7mt55bP5ekzzyVbvP+sxnv2XHvROLtYx7Qfw1bWu3rb6gWDu1pvn57LvfQY1lvv0Ml8T9pRDZYMe26ZlSFnvtvWu9ySvLDfH3/7fa4V13usfXwud0OtOKT1bnVbszbEzLvY143THDqa5C/W/P5Ekh+/0B+87ntP51/9998ZY5P9UFXZ6RFXAHC+qpX/5NkL+5afm/UAhmGwNRgAsL5xa7BxPq1svcOVXlLVVtWNVfVgVT04xrZ6oyr54Ysql128L7XjA7YAYMXqfuWHLyr7FbZqkDUYADA54xw59ESS16/5/XVJnjz/Tq21O5Lckayc7/5rP/lPx9jkbK1e7OqnRhe72u4nz3Tt5fuS/fv35fvPn5vJ9gF2u1cc3Jfl5XN5dkbT6OpFa/uyX+nE19836xEMweBqsL5RgwGMxzw6AWPWYOM0h76U5MqquiLJQpJ3J/nHY41myrZy8agLfdrE9VcdfWH5ep+AMamLUq2O6fB3v5b5+flNP40HgBdb+8kWJ0+ezOKrrlx3Hu3yIoOr6xhnv7LZthiMXV+D9cVO379ra7ALfRoPACsu9G/ZrX6iuNpnsnb8aWVJUlVvT/LhrHyM6kdba79xofvvf8Wr2oFXXvKDg6FbfvDMbmfZdu+/ZllbPvvc8plvL5xb+qtv7+Qx98xrk3xrvRv2HXrla/Zf/Jqjtf/Ay8bJq4vMd9V6V83wMbTls8+de27pu/teftGra9++A73J5rxl7dy5s+eefeY7+1526FUXfJ0lG27/hXVs97HO4HXTzp07myS1b9+Bmb7OV00yh0k/himvt507d3b5e9/6iwvM+xvOpbvJluf9CWd+9rtPZ/n73129FxOyoxrsVZfM9n05zW1daD7vpha8cA32Q699fS/2a9Pc1rjryAbrm+J4193X9yGb88e5lVpxvUy3+lh79BrpVa24qifZ7Ia5ZZP5duz6a6x/8+7BzM/+1Xg12FjNoW1vrOrB1tpbp7bBPU6e3ZNp92TaLXl2T6bdkmc/eV66Jc/uybRb8uyeTLslz+6Nm+k4F6QGAAAAYJfTHAIAAAAYsGk3h+6Y8vb2Onl2T6bdk2m35Nk9mXZLnv3keemWPLsn027Js3sy7ZY8uzdWplO95hAAAAAA/eK0MgAAAIABm0hzqKreVVVfqapzVfXWNcvfUFVLVfXw6Os/rLntLVX1SFU9VlX/tqp2/BFse9FGmY5uu3WU2+mqOrZmuUy3qKo+WFULa16bb19z27r5cmFVdd0os8eq6pZZj2e3qqpvjN7HD1fVg6Nlr6mqz1XV10bfXz3rcfZVVX20qp6uqkfXLNswP+/3zW2QqTm0J9Rg3VODTY65YzLUYONTf41PDda9Sddgkzpy6NEkP5vkgXVu+/PW2ptHX7+4ZvlHktyY5MrR13UTGttutW6mVfWmJO9O8iNZyex3qmr/6GaZbs9vr3lt/kGyab5sYJTRv0/yj5K8Kcl7RlmyM9eOXper/yi5Jcn9rbUrk9w/+p313ZmXzn3r5uf9vmV3Zv39iTm0H9Rg3VODTZa5o0NqsE6pv8ZzZ9RgXbszE6zBJtIcaq19tbV2eqv3r6rLkryytfaFtnIRpP+Y5PpJjG23ukCm70jysdbas621/53ksSRvk2ln1s13xmPaDd6W5LHW2tdba88l+VhWsqQb70hy1+jnu+K9vaHW2gNJvn3e4o3y837fgg0y3YhMp0wN1j012EyYO3ZODTY56q9tUIN1b9I12CyuOXRFVZ2qqj+qqp8cLTua5Ik193litIzNHU3yF2t+X81Optv3K1X15dHhequHOG6ULxcmt+60JH9YVQ9V1Y2jZZe21p5KktH3S2Y2ut1po/y8bsdjDu0/NVi31GDdMHd0S3bdUH9NhhpsMjqZRw/sdOtV9V+T/PA6N/2L1tqnNvizp5L8rdbaX1bVW5KcqKofSbLeediD+xi1HWa6UXYyPc+F8s3K4d8fykpGH0ryW0l+IXLcKbl155rW2pNVdUmSz1XVn816QHuY1+3OmUOnSA3WPTXY5Ki/pk523VB/TZfX7c51No/uuDnUWvsHO/ibZ5M8O/r5oar68yR/JytdrNetuevrkjy507HtVjvJNCvZvX7N76vZyfQ8W823qn43yadHv26ULxcmt4601p4cfX+6qj6ZlcNBv1lVl7XWnhqdvvD0TAe5+2yUn9ftDrXWvrn6szl08tRg3VODTY76a+pk1wH118SowTrWZQ021dPKqurI6kWQqupvZ+UCfV8fHVL2var6iaqqJD+XZKP/peHF7k3y7qp6eVVdkZVMvyjT7RlNTqvemZWLTyYb5Dvt8e1CX0pyZVVdUVUvy8rF0O6d8Zh2naq6qKp+aPXnJD+TldfmvUluGN3thnhvb9dG+Xm/75A5tP/UYBOhBhuTuWMi1GBjUn9NlBqsY13Oozs+cmiTAb4zyb9LciTJZ6rq4dbasSQ/leTXq+pskuUkv9haW72g0i9l5erbh5L8l9EXIxtl2lr7SlUdT/KnSc4m+eXW2vLoz2S6df+6qt6clUPtvpHkpiTZJF820Fo7W1W/kuS+JPuTfLS19pUZD2s3ujTJJ1f+bZEDSX6/tfbZqvpSkuNV9d4kjyd51wzH2GtVdXeS+SSvraonknwgyW1ZJz/v963ZINN5c2g/qMG6pwabKPVXx9RgnVB/dUAN1r1J12C18iEKAAAAAAzRLD6tDAAAAICe0BwCAAAAGDDNIQAAAIAB0xwCAAAAGDDNIQAAAIAB0xwCAAAAGDDNIQAAAIAB0xwCAAAAGLD/H/cM05rZMbhgAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 1440x360 with 4 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import math\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "# 定义一个函数，用于生成正弦波\n",
    "def getSin(amp, freq, phase, sampleList):\n",
    "    return amp * np.sin(-2 * math.pi * freq * sampleList + phase)\n",
    "\n",
    "# 定义一个函数，用于生成余弦波\n",
    "def getCos(amp, freq, phase, sampleList):\n",
    "    return amp * np.cos(-2 * math.pi * freq * sampleList + phase)\n",
    "\n",
    "#定义一个函数，把去噪的掩膜放进去\n",
    "def denoise(arr,thresh):\n",
    "    mask=arr>thresh\n",
    "    return arr*mask\n",
    "\n",
    "s=3000\n",
    "t=np.linspace(0,1,s)\n",
    "#分别生成四个正余弦波\n",
    "s1 = getSin(amp=1.5, freq=30, phase=0, sampleList=t)\n",
    "s2 = getCos(amp=3, freq=5, phase=0, sampleList=t)\n",
    "s3 = getSin(amp=10, freq=100, phase=0, sampleList=t)\n",
    "s4 = getCos(amp=20, freq=120,phase=0,sampleList=t)\n",
    "m = s1 + s2 + s3 + s4  # 将四个正余弦波相加，得到混合波形,干净混合波形\n",
    "\n",
    "#循环算法\n",
    "fCoefs1=np.zeros(s,dtype='complex')\n",
    "for f in range(s):\n",
    "    p=m*np.exp(-1j*2*math.pi*f*t)\n",
    "    fCoefs1[f]=np.sum(p)\n",
    "amp_list=2*np.abs(fCoefs1/s)\n",
    "freqs=np.fft.fftfreq(len(amp_list),1/s)\n",
    "amp_shift=np.fft.fftshift(amp_list)\n",
    "freq_shift=np.fft.fftshift(freqs)\n",
    "\n",
    "#fft.fft方法\n",
    "fCoefs2=np.fft.fft(m,s)\n",
    "amp_list1=2*np.abs(fCoefs2/s)\n",
    "freqs1=np.fft.fftfreq(len(amp_list1),1/s)\n",
    "amp_shift1=np.fft.fftshift(amp_list1)\n",
    "freq_shift1=np.fft.fftshift(freqs1)\n",
    "\n",
    "fg,ax=plt.subplots(2,2,figsize=(20,5))\n",
    "ax[0,0].grid()\n",
    "ax[0,0].stem(freq_shift,amp_shift)\n",
    "ax[0,0].set_xlim([-150,150])\n",
    "ax[0,0].set_ylim([-0.5, 21])\n",
    "denoise(amp_shift,1)\n",
    "amp_shift[(freq_shift > 110) | (freq_shift < -110)] = 0\n",
    "ax[0,1].grid()\n",
    "ax[0,1].stem(freq_shift,amp_shift)\n",
    "ax[0,1].set_xlim([-150,150])\n",
    "ax[0,1].set_ylim([-0.5, 21])\n",
    "\n",
    "ax[1,0].grid()\n",
    "ax[1,0].stem(freq_shift1,amp_shift1)\n",
    "ax[1,0].set_xlim([-150,150])\n",
    "ax[1,0].set_ylim([-0.5, 21])\n",
    "denoise(amp_shift1,1)\n",
    "amp_shift1[(freq_shift1 > 110) | (freq_shift1 < -110)] = 0\n",
    "ax[1,1].grid()\n",
    "ax[1,1].stem(freq_shift1,amp_shift1)\n",
    "ax[1,1].set_xlim([-150,150])\n",
    "ax[1,1].set_ylim([-0.5, 21])\n",
    "plt.show()\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
